<!DOCTYPE html>
<html>

<head>
    <meta charset='utf-8'>
    <meta http-equiv='X-UA-Compatible' content='IE=edge'>
    <title>006-分割回文串</title>
    <meta name='viewport' content='width=device-width, initial-scale=1'>

</head>

<body>
    <div class="box">
        <div class="left-wrap">

        </div>
    </div>
</body>
<script>
    /*
    给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

    返回 s 所有可能的分割方案。

    示例:

    输入: "aab"
    输出:
    [
    ["aa","b"],
    ["a","a","b"]
    ]
    */
    /**
    * @param {string} s
    * @return {string[][]}
    */
    var partition = function (s) {
        debugger
        let dp = isPalindrome(s)
        console.log(dp)
        let ans = []
        function dfs(router) {
            if (router.length > 0 && router[router.length - 1][1] == s.length - 1) {
                ans.push(router)
                return
            }
            let row = router[router.length - 1]
            for (let j = row[1] + 1; j < s.length; j++) {
                if (dp[row[1] + 1][j]) {
                    dfs([...router].concat([[row[1] + 1, j]]))
                }
            }
        }

        for (let j = 0; j < s.length; j++) {
            if (dp[0][j]) dfs([[0, j]])
        }

        return ans.map((item) => {
            return item.reduce((pre, k) => {
                return pre.concat([s.substr(k[0], k[1] - k[0] + 1)])
            }, [])
        })
    };
    function isPalindrome(s) {
        let dp = new Array(s.length)
        for (let i = 0; i < dp.length; i++) {
            dp[i] = new Array(s.length).fill(false)
        }
        for (let l = 1; l <= s.length; l++) {
            for (let i = 0; i <= s.length - l; i++) {
                let j = i + l - 1
                dp[i][j] = s[i] == s[j] && (l < 3 || dp[i + 1][j - 1])
            }
        }
        return dp
    }
    console.log(partition('ABB'))
</script>

</html>